package person.bing.fbcloud.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: mengfanbing
 * @date: 2020/9/22 9:43
 */
public class Q22 {
    public static void main(String[] args) {

        System.out.println(generateParenthesis(1));
    }
    public static List<String> generateParenthesis(int n) {
        //1.列举所有组合
        //2.借助栈判断是不是有效的组合
        List<String> ans = new ArrayList<>();
        generateAll(new char[n*2],0,ans);
        return ans;

    }
    public static void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }
    //判断是否有效的括号组合
    public static Boolean valid(char[] chars) {
        Stack<Character> stack = new Stack<>();
        for (char ch:chars){
            if (stack.isEmpty()){
                stack.push(ch);
            }else {
                if (stack.peek().equals('(') && ch == ')'){
                    stack.pop();
                }else {
                    stack.push(ch);
                }
            }
        }
        if (stack.isEmpty()){
            return true;
        }else {
            return false;
        }
    }



}
